//: [Previous](@previous)

/*:
 数据
 * 数据对象
    * 数据元素
        * 数据项
        * 数据项...
    * 数据元素...
 */

/*:
 逻辑结构：
 * 集合结构
 * 线性结构
 * 树结构
 * 图结构
 
 物理结构：
 * 顺序存储结构
 * 链式存储结构
 */

//: 1+2+3+...+100
// 转换思路呀 不是循环
// 1+2+3+...100
// + 100+99+98+...1
// = 101+101+101+...+101
// 101 * 100 / 2
var sum = 0
var n = 100
sum = (1+n)*n/2

/*:
 算法的特性
 * 输入: 0个或多个输入
 * 输出: 至少有一个输出
 * 有穷性: 算法不会出现无限循环，一定会在一定的步骤后执行完毕
 * 确定性: 算法不会出现同一输入产生不同的输出
 * 可行性: 算法每一步都是可行的，可以再一定次数完成
 
 算法的设计的要求
 * 正确性
 * 可读性
 * 健壮性
 * 高效性
 * 低存储量
 */

/*:
 时间复杂度
 
 O(1): 常数阶
 O(n): 线性阶
 O(logn): 对数阶   2log2n+3
 O(n^2): 平方阶    2n^2+2n+1
 O(nlogn): nlogn阶 2n+3nlogn+19
 O(n^3): 立方阶
 O(n^n): 指数阶
 
 推导大O阶：
 1. 用常数1替代运行时间中的加法常数
 2. 在修改后的运行次数函数中，只保留最高阶项
 3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数
 */

/*:
 空间复杂度
 
 */


/*:
 ## 树
 度：结点拥有的子树数
 
 1. 结点:
 * 叶结点( Leaf )/终端结点：度为 0 的结点
 * 非终端结点/分支结点：度不为 0 的结点
    * 根结点
    * 内部结点
 树的度是树内各结点的度的最大值
 
 2. 层次
 结点的层次( Level ): 从根结点开始，根为第一层，根的孩子为第二层
 树的深度( Depth )/高度: 树中结点的最大层次
 
 ### 二叉树
 1. 斜树
 2. 满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层
 3. 完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号i与同样深度的满二叉树中编号i的结点在二叉树中的位置相同
 
 #### 二叉树的性质
 1. 在二叉树的第i层上至多有 2^(i-1) 个结点
 2. 深度为k的二叉树至多有 2^k - 1 个结点
 3. 对任何一颗二叉树T，如果其终端结点个数为n0，度为2的结点数为n2，则n0 = n2+1
 4. 具有n个结点的完全二叉树的深度为 log2n+1
 5. 如果一颗有n个结点的完全二叉树的d结点按层序编号(从第1层到第 log2n+1 层，每层从左到右)，对任一结点i有：
    * 如果 i=1，则结点i是二叉树的根，无双亲；如果 i>1，则其双亲是结点 [i/2]
    * 如果 2i>n，则结点i无左孩子(结点i为叶子结点); 否则其左孩子是结点2i
    * 如果 2i+1>n，则结点i无右孩子; 否则其右孩子是结点2i+1
 
 #### 二叉树的遍历
 * 前序遍历：根结点 ---> 左子树 ---> 右子树
 * 中序遍历：左子树---> 根结点 ---> 右子树
 * 后序遍历：左子树 ---> 右子树 ---> 根结点
 * 层次遍历：只需按层次遍历即可
 

 
 */



//: [Next](@next)
